package bintree.heap.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 最小的K个数
 * @author yuisama
 * @date 2022/05/17 21:17
 **/

//class IntegerReverse implements Comparator<Integer> {
//    @Override
//    public int compare(Integer o1, Integer o2) {
//        return o2 - o1;
//    }
//}


public class Num17_14_SmallestK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr.length == 0 || k == 0) {
            return ret;
        }
        // JDK默认是一个最小堆,需要改成一个最大堆
        // Lambda表达式
        Queue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);
//        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
        // 遍历原集合，队列只保存k个元素
        for (int i = 0; i < arr.length; i++) {
            if (queue.size() < k) {
                queue.offer(arr[i]);
            }else {
                int max = queue.peek();
                if (arr[i] < max) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        // 此时队列中就保存了前k个最小值元素,依次出队即可
        int i = 0;
        while (!queue.isEmpty()) {
            ret[i ++] = queue.poll();
        }
        return ret;
    }
}